package selected;

import java.util.*;

public class J0827 {
    // 1.LRU缓存
    class LRUCache {
        class DLinkedList{
            int key;
            int value;
            DLinkedList prev;
            DLinkedList next;
            public DLinkedList(){};
            public DLinkedList(int key, int value){
                this.key = key;
                this.value = value;
            }
        }
        private Map<Integer, DLinkedList> cache = new HashMap<>();
        private  int capacity = 0, size = 0;
        private  DLinkedList head = new DLinkedList();
        private  DLinkedList tail = new DLinkedList();

        public LRUCache(int capacity) {
            size = 0;
            this.capacity = capacity;
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedList node = cache.get(key);
            if(node == null){
                return -1;
            }
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedList node = cache.get(key);
            if(node == null){
                node = new DLinkedList(key, value);
                addToHead(node);
                cache.put(key, node);
                size++;
                if(size > capacity){
                    DLinkedList tail = removeTail();
                    cache.remove(tail.key);
                    size--;
                }
            } else {
                node.value = value;
                moveToHead(node);
            }
        }
        public void addToHead(DLinkedList node){
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }
        public DLinkedList removeTail(){
            DLinkedList node = tail.prev;
            remove(node);
            return node;
        }
        public void remove(DLinkedList node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        public void moveToHead(DLinkedList node){
            remove(node);
            addToHead(node);
        }
    }
    // 2.二叉树的中序遍历
    public List<Integer> inorder(TreeNode root, List<Integer> ret){
        if(root == null) return ret;
        inorder(root.left, ret);
        ret.add(root.val);
        inorder(root.right, ret);
        return ret;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        inorder(root, ret);
        return ret;
    }

    // 3.二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftLength = maxDepth(root.left);
        int rightLength = maxDepth(root.right);
        return Math.max(leftLength , rightLength) + 1;
    }
    // 4.翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    // 5.对称二叉树
    public boolean symmetric(TreeNode left, TreeNode right){
        if(left != null && right == null
                || left == null && right != null) return false;

        if(left == null && right == null) return true;

        if(left.val != right.val) return false;
        return symmetric(left.left, right.right)
                && symmetric(left.right, right.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return symmetric(root.left, root.right);
    }

    // 6.二叉树的最大直径
    int ret = 0;
    public int binary(TreeNode root){
        if(root == null) return 0;
        int leftRoot = binary(root.left);
        int rightRoot = binary(root.right);
        ret = Math.max(leftRoot + rightRoot, ret);
        return Math.max(leftRoot, rightRoot) + 1;
    }
    public int diameterOfBinaryTree(TreeNode root) {
        binary(root);
        return ret;
    }
    // 7.二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while(size-- > 0){
                TreeNode top = queue.poll();
                tmp.add(top.val);
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
            }
            ret.add(tmp);
        }
        return ret;
    }
}
